package com.java.linkedlist;

import java.util.Objects;

/**
 * 约瑟夫问题
 * 从一个位置开始，以 m 的步长，将节点移除，直至剩余一个节点
 * @author 19252
 */
public class Josephus {

    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.createCircle(5);
        circleSingleLinkedList.showCircleList();
        // 约瑟夫问题演示
        System.out.println("================> 约瑟夫问题演示 <=================");
        circleSingleLinkedList.solutionJosephus(2, 2, 5);
    }
}

/**
 * 环形单链表
 */
class CircleSingleLinkedList {
    /**
     * 初始头结点未赋值状态
     */
    private CircleNode head = null;

    /**
     * 直接创建一个环形链表，根据你输入的数字的大小
     * @param num 链表节点个数
     */
    public void createCircle(int num){
        // 输入数字的简单校验
        if (num < 1){
            System.out.println("您输入的数字不能构成环形链表！");
            return;
        }
        // 最短环形链表
        if (num == 1){
            head.setNo(1);
            head.setNext(head);
            return;
        }
        // 正常环形链表的生成
        head = new CircleNode(1);
        head.setNext(head);
        CircleNode currentNode = head;
        for (int i = 2; i <= num; i++) {
            CircleNode circleNode = new CircleNode(i);
            // 节点加入环形链表
            currentNode.setNext(circleNode);
            // 将加入的节点的下一指向head
            circleNode.setNext(head);
            // 辅助指针currentNode 向后移动到最新加入的节点
            currentNode = circleNode;
        }
    }

    /**
     * 环形链表的遍历
     */
    public void showCircleList(){
        CircleNode currentNode = head;
        // 链表判空
        boolean flag = Objects.nonNull(currentNode);
        if (flag){
            // 输出格式化
            System.out.printf("链表节点 %d \n" , currentNode.getNo());
        }else {
            System.out.println("链表为空！");
            return;
        }
        flag = Objects.nonNull(currentNode.getNext());
        while (flag){
            currentNode = currentNode.getNext();
            // 回到头结点，终止输出
            if (Objects.equals(currentNode, head)){
                return;
            }
            System.out.printf("链表节点 %d \n" , currentNode.getNo());
            flag = Objects.nonNull(currentNode.getNext());
        }
    }

    /**
     * 解决约瑟夫问题
     * @param no 起始节点
     * @param m 步长
     * @param length 该链表的长度
     */
    public void solutionJosephus(int no, int m, int length){
        // 起始节点，或当前节点的前一个节点
        CircleNode pre = head;
        CircleNode current = head;
        // 链表及输入合法化的判断
        if (length < 1 || no > length || m < 1) {
            System.out.println("您的输入有误，请检查！");
            return;
        }
        boolean flag = Objects.equals(pre.getNext(), current);
        if (flag){
            System.out.println("链表中只有一个节点！");
            return;
        }
        // 校验合法之后，进行节点的移动，将节点移动起始输入的节点
        for (int i = 0; i < length; i++) {
            if (no == pre.getNext().getNo()){
                // 起始节点，赋值
                current = pre.getNext();
                System.out.printf("--->起始节点 %d \n", current.getNo());
                System.out.printf("--->起始pre %d \n", pre.getNo());
                break;
            }
            // 因为这里用于实验的链表是连续生成的，
            // 就不需要在这里进行，循环退出设置
            pre = pre.getNext();
        }
        while (!flag){
            for (int i = 0; i < m; i++) {
                pre = pre.getNext();
                current = current.getNext();
            }
            System.out.printf("移出节点 %d \n", current.getNo());
            current = current.getNext();
            pre.setNext(current);
            flag = Objects.equals(current, current.getNext());
        }
        System.out.printf("最后节点 %d \n", current.getNo());
    }
}

/**
 * 环形链表节点
 */
class CircleNode {

    /**
     * 节点编号
     */
    private int no;

    /**
     * 下一指针
     */
    private CircleNode next;

    public CircleNode() {
    }

    public CircleNode(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public CircleNode getNext() {
        return next;
    }

    public void setNext(CircleNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "CircleNode{" +
                "no=" + no +
                '}';
    }
}
